\documentclass[11pt]{article}

\usepackage{standalone}
\standalonetrue
\usepackage{estilo}

\title{ABM}
\author{Ricardo Cruz}

\begin{document}

\ifstandalone
\maketitle
\fi

\section{Introduction}

At the other end of the spectrum, \textbf{\glspl{ABM}} are mini-models where what is modeled are individuals (or agents) and not aggregates. This paradigm turns things upside-down; each individual in the model stores its properties, rather than individuals being categorized in compartments. It is a more natural paradigm for domain experts because it is logically structured closer to the phenomenon at study. It is a more direct reality-model mapping. Other advantages are that \glspl{ABM} allow us to trace the fate of a particular agent; also, \glspl{ABM} can easily associate continuous quantities to an agent; these quantities have to be discretized for most other mathematical models. Continuous variables are possible using \glspl{PDE}, but easily become unmanageable and numerical integration boils down to discretization. Their complexity depends heavily on the implementation, but, usually, particle simulators (which can be seen as a type of \gls{ABM}) have execution times of time complexity $O(n^2)$, and space complexity of $O(n)$ \citep{stochsim}. Interestingly, here $n$ refers to the number of agents, not of compartments as in a system of \glspl{ODE} or reactions as in the \gls{CTMC} method we will see below; so it is conceivable that an \glspl{ABM} is faster than a \gls{ODE} model for very small population that has too many properties that need compartmentalizing. If we would like to add a new agent property, whose value range is $k$, to an \gls{ODE} model, it will require $n(k-1)$ new compartments, increasing by that order of magnitude the complexity of the numerical integrator algorithm. Viewed in another way, in \glspl{ABM} we iterate agents; in \glspl{ODE} we iterate variables. \footnote{Talvez interessante explorar um pouco esta diferença de complexidades.} \glspl{ODE} do have the advantage that, being deterministic, a single run is enough to produce the desirable statistics; furthermore conclusions, and sometimes results, can be obtained analytically for the simpler models. Computation gains may be obtained through the usage of distributed computing techniques. \emph{(See section \ref{ABM}.)}






\section{More Introduction}

\Glspl{ABM} are computer models representing and simulating the actions and interactions of autonomous agents (be they firms and government in an economy, or cells and molecules in the immune system in our case). In the case of the immune system, they are sometimes referred as Artificial Immune Systems (AISs). \Glspl{ABM} try to reproduce the real phenomenon in the computer, and so are often used to synthesize and test the congruence of theories. Drawbacks of \glspl{ABM} are that they scale poorly, and require firm theoretical foundations and empirical data for simulation parametrization. For example, \citet{Kirschner2007} studies antigen presentation within the immune system.





\section{UML programming language}

Usually, \gls{ABM} models are implemented in an imperative (or procedural) language, be it a generic language like C or Java or a more specific language such as Netlogo or toolkit such as Java/Repast. Such languages are structured as a recipe, or series of steps, usually called scripts, lacking (to a lesser or greater degree) higher-level constructs for how the program is structured and behaves. Any modern high-level language allows these steps to be structured into functions, a formalism expressing a self-contained means of associating transformations of input into output. Matlab, for instance, forces the programmer to structure his project into files, whereby each file may contain either a single function or be a script without any function. Object-oriented programming languages, such as Java, go one step further by including structures such as \texttt{class} that provide formal means of expressing manipulation of data blocks through functions within said \texttt{class}. Java, in particular, forces programmers to structure their project in files, whereby each file is one class of the program. Furthermore, these languages, offer keywords such as \texttt{public} and \texttt{private} constructors, among others, allowing further expression of what level components are visible and so allow for stronger analytical introspection. Of course all these constructs are unnecessary for developing a computer program; any modern program could be programmed as a script, since ultimately it will be broken down to a series of steps in machine code. The objective of every one of these constructs is to layer computer programs, allowing the navigation and introspection of the program, making programs more robust and easier to build ever more sophisticated software. Of course, no language is programmer-proof; any optional constructs can go unused, and any enforcement mechanism can be circumvented. Ultimately, developing computer programs is an art.

Unified Modelling Language (UML) is a standard for the development of computer programs using a diagrammatic language, an ISO standard since 2000, promising means of an even more refined layering of computer programs, very popular especially in embedded systems where programming errors are more costly. Its use has been explored in the field of computer biology for its rigor as a language where it is paramount that research results are not affected by bad programming, as well as allowing means to expose only layer slices for publication, hiding more mundane lower levels parts of the computer simulation. Being a diagrammatic language also eases communication between domain experts and modeling experts. UML standard defines how the diagrams may be convert into modern computer languages. The standard is divided into two parts: 4 diagram schemes for the static representation of the computer program (e.g. structure of the program into classes, functions and variables); 5 diagrams for dynamical modeling that actually specifies program behavior by modeling for instance, how variables change given a stimulus. Following \citet{Read2014}, we will briefly present how UML may be used for biological systems, and will apply it to any papers discussed in the rest of the thesis, when sensible. At the static level, class diagram will be used for describing system organization, while at the dynamic levels, we will discuss the sequence diagram, activity diagram and state machine diagram.

\tikzstyle{cell} = [draw, ellipse, node distance=4.2ex and 4em, line width=1pt, font=\bf]
\tikzstyle{transition} = [font=\small]
\tikzstyle{line} = [draw, thick, ->, line width=1pt]
\tikzstyle{class} = [draw,minimum size=1.4em]

% tikz tipos de arrows:
% http://tex.stackexchange.com/questions/42611/list-of-available-tikz-libraries-with-a-short-introduction/42679#42679

\begin{figure}[htp]
\begin{subfigure}[t]{0.18\linewidth}
\centering
\begin{tikzpicture}
\node [class] (s0) {A};
\node [class, below=of s0] (s1) {B};
\path [draw, -{stealth}] (s0) -- (s1) node [transition,pos=1,right,xshift=-0.2em,yshift=1.2ex] {1};
\end{tikzpicture}
\caption{Uni-directional association}
\end{subfigure}
\begin{subfigure}[t]{0.18\linewidth}
\centering
\begin{tikzpicture}
\node [class] (s0) {A};
\node [class, below=of s0] (s1) {B};
\path [draw, -] (s0) -- (s1) node [transition,pos=1,right,xshift=-0.2em,yshift=1.2ex] {*} node [transition,pos=0,right,xshift=-0.2em,yshift=-1.3ex] {0..1};
\end{tikzpicture}
\caption{Bi-directional association}
\end{subfigure}
\begin{subfigure}[t]{0.18\linewidth}
\centering
\begin{tikzpicture}
\node [class] (s0) {A};
\node [class, below=of s0] (s1) {B};
\path [draw, -{diamond}] (s0) -- (s1) node [transition,pos=1,right,xshift=-0.2em,yshift=1.2ex] {1} node [transition,pos=0,right,xshift=-0.2em,yshift=-1.3ex] {*};
\end{tikzpicture}
\caption{Aggregation}
\end{subfigure}
\begin{subfigure}[t]{0.18\linewidth}
\centering
\begin{tikzpicture}
\node [class] (s0) {A};
\node [class, below=of s0] (s1) {B};
\path [draw, -{open diamond}] (s0) -- (s1) node [transition,pos=1,right,xshift=-0.2em,yshift=1.2ex] {1} node [transition,pos=0,right,xshift=-0.2em,yshift=-1.3ex] {*};
\end{tikzpicture}
\caption{Composition}
\end{subfigure}
\begin{subfigure}[t]{0.18\linewidth}
\centering
\begin{tikzpicture}
\node [class] (s0) {A};
\node [class, below=of s0] (s1) {B};
\path [draw, -{open triangle 60}] (s0) -- (s1);
\end{tikzpicture}
\caption{Generalization}
\end{subfigure}
\caption{Tipos de associações no UML para o diagrama de classes. (preciso completar as setas quando atualizar o tikz ...)}
\label{fig:class}
\end{figure}

\begin{lstlisting}[language=java]
class A {    (*@ \tikzmark{ode}{} @*)
}  (*@ \tikzmark{pde}{} @*)
class B {    (*@ \tikzmark{sde}{} @*)
	List <A> list_a;  (*@ \tikzmark{cmtc}{} @*)
}  (*@ \tikzmark{abm}{} @*)
class C extends A {
}
\end{lstlisting}

\begin{tikzpicture}[overlay, remember picture]
  \draw [decoration={brace,amplitude=0.5em},decorate,ultra thick,black]
    let \p1=(ode), \p2=(pde), \p3=(cmtc) in
    ({\x3+2em}, {\y1+0.8em}) -- node[right=0.6em] {deterministic} ({max(\x1,\x2,\x3)+2em}, {\y2});
  \draw [decoration={brace,amplitude=0.5em},decorate,ultra thick,black]
    let \p1=(sde), \p2=(abm), \p3=(cmtc) in
    ({\x3+2em}, {\y1+0.8em}) -- node[right=0.6em] {stochastic} ({\x3+2em}, {\y2});
\end{tikzpicture}

No \textbf{diagrama de classes}, figura \ref{fig:class}, a relação entre as classes (entidades) é estabelecida pelas seta descritas. As duas primeiras setas indicam associações de dependência, sendo que na primeira, a classe A tem uma referência para B, podendo aceder às propriedades da mesma e chamar ou enviar eventos para B. Em c) e d), a classe A gere as instâncias da classe B na memória; no caso da agregação, a classe A é a única a fazê-lo pelo que se essa classe for destruída, também serão perdidas as instâncias de B. Por último, a generalização implica que a estrutura da classe A é uma extensão à estrutura da classe B.

\begin{figure}
\centering
\begin{tikzpicture}
\node [class] (s0) {a criar ..};
\end{tikzpicture}
\label{fig:statechart}
\caption{Diagrama UML de transição de estados.}
\end{figure}

O \textbf{diagrama de transição de estados}, inspirado nos statecharts de Harel \cite{statecharts}, será a nossa principal ferramenta para modelar o funcionamento do sistema, inspirados pelo trabalho do mesmo autor das statecharts \cite{harel-lymphnode}.






\section{General purpose artificial immune systems}
\label{immsim}

The grandfather of all agent-based lymph node simulations is ImmSim by Ceiden and Selada. It is the most revered and referenced simulation. Space is discretized in a grid and diffusion happens in the fashion of Brownian motions, without a realistic concern for chemotaxis. When two agents collide, they interact according to a few rules. For instance, a free virion may be captured by a macrophage. A helper T cell then may become stimulated when interacting with the macrophage. Specificities are implemented using bit-strings --- these are probabilities that two colliding agents will successful interact. Several expected behavior may be modeled in qualitative terms, such as the effect of vaccination.

Several other general purpose immune systems have been inspired by this work: ImmSim3, C-ImmSim, Simmune, SIS, AbAIS, ParImm, CAFISS and ImmunoGrid. Some of them adding such things as a third space dimension. The idea of these simulations does not seem to produce statistically valid results, but merely to validate possible trajectories against theory.





\section{David Harel --- statecharts \& UML}

David Harel's usage of statecharts is particularly interesting. Using discrete variables of finite range --- we shall call them hereby state variables. Statemachines are graphs or tuples describing possible transitions between values of the state variable, depending on external events (such as changing state to activated after the T cell being presented antigen), and whose transitions may have associated actions. Statecharts are functionally identical to statemachines, but are more succinct in expression, since they allow for the embedding of states within another parent state --- this means that two transitions from a source to a destination state can be condensed into a single transition by embedding the source state into another state. The main benefit of using this approach for state variables is that it allows for a machine and even a graphical representation easily accessible for the study of the model by knowledge-domain experts. David Harel has one general purpose immune system simulator by the name of GemCell. In his works, he uses state variables as most as possible, to take advantage of statecharts, but he also makes use of continuous variables for spatial dynamics, though sometimes regions are modeled as state variables. His papers are inspirational, but unfortunately impossible to implement because his statecharts are not provided and the model is not well documented.




\section{Lin Shau model}

Some authors have preferred to test specific parts of the theory in ad-hoc models, usually partially inspired by cellular automata models.

One such model that managed to implement HIV three phases is this model by \citet{Lin2010} \footnote{I have it implemented at: \url{https://www.dropbox.com/s/sjwykjn2t9cx0hk/linshuai.jar?dl=0}}. This is a reproduction of the paper in succinct format: the agents properties are represented using an UML class diagram, and the algorithm is represented in pseudo-code afterwards.


\tikzstyle{class} = [rectangle, draw=black, text centered, anchor=north, text=black, text width=8em]
\tikzstyle{inherits} = [open triangle 90-]

\noindent
\begin{center}
\begin{tikzpicture}[node distance=8em]
\node (agent) at (0,0) [class, rectangle split, rectangle split parts=2]
{
	\textbf{Agent}
	\nodepart[align=left]{second}+ specificity : int
};      
\node [right=of agent] (cd4) [class, rectangle split, rectangle split parts=2, text width=11em,yshift=+1em] {
	\textbf{CD4}
	\nodepart[align=left]{second}+ virus-specificity : int \newline + virus-nbr : int
};      
\node [left=of agent] (cd8) [class, rectangle split, rectangle split parts=2,yshift=+1em] { \textbf{CD8} };      
\node [left=of agent] (hiv) [class, rectangle split, rectangle split parts=2,xshift=+1em,yshift=-2em] { \textbf{HIV} };

\draw[inherits] (agent.east) -| (cd4.west);
\draw[inherits] (agent.west) -| (cd8.east);
\draw[inherits] (agent.west) -| (hiv.east);
\end{tikzpicture}
\end{center}



At each step, the following rules are processed:

\begin{multicols}{2}
\begin{algorithmic}[1]
	\FORALL{agents}
		\STATE{move at most rm}
		\IF{same type there}
			\STATE{swap them}
		\ENDIF
	\ENDFOR
	\FORALL{hiv+cd4}
		\IF{cd4 not infected}
			\IF{Phamming(p0)}
				\STATE{proliferate nx within range rx, if none there}
			\ENDIF
		\ENDIF
		\IF{P(pv)}
			\IF{P=mv}
				\STATE{virus mutation; one bit flips}
			\ENDIF
			\STATE{virus gets integrated into the cell}
		\ENDIF
	\ENDFOR
	\FORALL{cd4}
		\IF{cd4 infected}
			\IF{P(bv)}
				\STATE{virus++}
			\ENDIF
			\IF{internal virus == nlys}
				\STATE{cell dies}
				\STATE{proliferate nlys virus within range rv, if none there}
			\ENDIF
		\ENDIF
	\ENDFOR
	\FORALL{cd8+cd4}
		\IF{cd4 infected and has virus \textgreater 0}
			\IF{Phamming(p0\_)}
				\STATE{cd8 proliferates}
			\ENDIF
			\IF{Phamming(k0)}
				\STATE{cd4 killed}
			\ENDIF
		\ENDIF
	\ENDFOR
	\FORALL{virus and cd8}
		\IF{hiv and P=dvi=dv0+(1-dv0)*cd4Hill(i)}
			\STATE{virus of strain i dies}
		\ENDIF
		\IF{cd8 and P=dyi=dy0*(1-cd4Hill(i))}
			\STATE{cd8 of strain i dies}
		\ENDIF
	\STATE{create cd4 n=x0*dx0 at random pos, if none there}
	\STATE{create cd8 n=y0*dy0 at random pos, if none there}
	\ENDFOR
\end{algorithmic}
\end{multicols}

In conclusion, the disease works in defeating our immunity because at the beginning there is a wide range of T-cell specificities, but only one hiv specificity. HIV kills all Th indiscriminately, but it also (indirectly) ``binds'' and stimulates Th (and, by proxy, Tc) to proliferate. Tc start killing free HIV virions. The system has much difficulty completely eliminating every trace of HIV at any moment, which means that, as mutations accumulate, the system starts working less well and less well. In conclusion, there is an asymmetry in that HIV ``binds'' to any Th, but Th and Tc only ``bind'' to specific HIV.




\section{Event-driven versus time-driven simulation}



\section{Summary}

In agent-based modeling, antigens (such as HIV) are traditionally modeled as agents --- but sometimes the space is discretized in a grid and free virions are modeled, together with antibodies and cytokines as values within each square of the grid. This is necessary because of the stupendous count scale; and the fact no realism is lost because HIV molecules lack any kinetic logic (or so we think). The only logic needed to be implemented therefore are fluid dynamics and cell response to fluid molecules. Cytokines may also be implemented as fluids (as they often are), with a very limited range, since they are captured by cellular receptors and also degrade.





%%% END

\ifstandalone
\printglossary
\printbibliography
\fi

\end{document}
